淺談 C# 的 GetHashCode()

TLDR

• 覆寫 Equals() 時，必須同時覆寫 GetHashCode()，否則 Dictionary 或 HashSet 等依賴雜湊的集合將無法正確識別相等物件。
• GetHashCode() 實作原則：若兩個物件 Equals() 為 true，則其 GetHashCode() 必須相同；反之則不強制要求不同。
• 推薦使用 HashCode.Combine() 實作雜湊碼，以確保分布均勻並減少碰撞。
• Dictionary 透過 GetHashCode() 快速定位 Bucket，再透過 Equals() 確認內容，這種機制能顯著提升搜尋效率。

---

為什麼必須同時覆寫 Equals 與 GetHashCode

在 C# 中，Dictionary<TKey, TValue>、HashSet<T> 以及 LINQ 的 Distinct() 等方法，皆依賴物件的雜湊值來判斷元素是否存在或是否重複。

什麼情況下會遇到這個問題： 當你自訂類別並覆寫了 Equals() 方法，卻遺漏了 GetHashCode() 時，即使兩個物件的屬性值完全相同，集合類別仍會將它們視為不同的物件。

踩雷範例

以下程式碼展示了僅覆寫 Equals() 的錯誤行為：

public class Test {
    public string Name { get; set; }
    public int Age { get; set; }

    public override bool Equals(object obj) => obj is Test test && Name == test.Name && Age == test.Age;
}

// 測試執行
Test test1 = new() { Name = "王大明", Age = 10 };
Test test2 = new() { Name = "王大明", Age = 10 };

Dictionary<Test, string> dic = new() { [test1] = "測試" };

Console.WriteLine(test1.Equals(test2)); // 輸出: True
Console.WriteLine(dic.ContainsKey(test2)); // 輸出: False

原因分析：Dictionary 在執行 ContainsKey 時，會先呼叫 GetHashCode() 取得雜湊值以定位儲存桶（Bucket）。由於未覆寫 GetHashCode()，系統會使用預設的物件參考雜湊碼，導致 test1 與 test2 產生不同的雜湊值，進而判定為不同鍵值。

---

GetHashCode 的實作建議

使用 HashCode.Combine (推薦)

針對 .NET Core 2.1 以上版本，建議使用 HashCode.Combine()，它能自動處理多個欄位的雜湊組合，並保持良好的分布性。

public override int GetHashCode() => HashCode.Combine(Name, Age);

針對舊版 .NET Framework

若環境不支援 HashCode.Combine()，可手動實作並使用質數進行運算，以減少雜湊碰撞：

public override int GetHashCode() {
    int hashCode = -1360180430;
    hashCode = hashCode * -1521134295 + EqualityComparer<string>.Default.GetHashCode(Name);
    hashCode = hashCode * -1521134295 + Age.GetHashCode();
    return hashCode;
}

實作原則

• GetHashCode() 絕對不可拋出例外。
• 使用 EqualityComparer<T>.Default 計算屬性雜湊值，可妥善處理 null 值並確保規則一致。

---

Dictionary 搜尋機制解析

什麼情況下會遇到這個問題： 當開發者需要理解 Dictionary 如何在海量資料中維持高效能搜尋時，必須了解其內部 FindValue 的運作邏輯。

Dictionary 內部維護兩個關鍵陣列：

• _buckets：儲存雜湊值運算後的索引。
• _entries：儲存實際的 TKey、TValue 以及下一個節點的索引。

搜尋流程

1. 計算 HashCode：透過 key.GetHashCode() 快速定位 _buckets 中的索引。
2. 初步篩選：比較 entry.hashCode 與目標雜湊值，若不相等則直接跳過，避免昂貴的 Equals() 呼叫。
3. 碰撞處理：若雜湊值相同但物件不同（發生碰撞），則透過 entry.next 鏈結串列逐一比對，直到找到目標或遍歷結束。

此機制確保了 Dictionary 在大多數情況下能達到接近 O(1) 的搜尋複雜度。

---

異動歷程

1. 2024-09-01

   • 初版文件建立。